<template><div><h1 id="_2、两数相加-中等" tabindex="-1"><a class="header-anchor" href="#_2、两数相加-中等" aria-hidden="true">#</a> 2、两数相加-中等</h1>
<h2 id="简介" tabindex="-1"><a class="header-anchor" href="#简介" aria-hidden="true">#</a> 简介</h2>
<p>给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。<br>
请你将两个数相加，并以相同形式返回一个表示和的链表。<br>
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
<strong>示例1</strong></p>
<div class="language-javascript ext-js line-numbers-mode"><pre v-pre class="language-javascript"><code>输入：l1 <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">,</span><span class="token number">3</span><span class="token punctuation">]</span><span class="token punctuation">,</span> l2 <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">5</span><span class="token punctuation">,</span><span class="token number">6</span><span class="token punctuation">,</span><span class="token number">4</span><span class="token punctuation">]</span>
输出：<span class="token punctuation">[</span><span class="token number">7</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">8</span><span class="token punctuation">]</span>
解释：<span class="token number">342</span> <span class="token operator">+</span> <span class="token number">465</span> <span class="token operator">=</span> <span class="token number">807</span>
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p><strong>示例2</strong></p>
<div class="language-javascript ext-js line-numbers-mode"><pre v-pre class="language-javascript"><code>输入：l1 <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span><span class="token punctuation">,</span> l2 <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span>
输出：<span class="token punctuation">[</span><span class="token number">0</span><span class="token punctuation">]</span>
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div></div></div><p><strong>示例3</strong></p>
<div class="language-javascript ext-js line-numbers-mode"><pre v-pre class="language-javascript"><code>输入：l1 <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">9</span><span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">]</span><span class="token punctuation">,</span> l2 <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token number">9</span><span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">]</span>
输出：<span class="token punctuation">[</span><span class="token number">8</span><span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">,</span><span class="token number">9</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">0</span><span class="token punctuation">,</span><span class="token number">1</span><span class="token punctuation">]</span>
解释：<span class="token number">9999999</span> <span class="token operator">+</span> <span class="token number">9999</span> <span class="token operator">=</span> <span class="token number">10009998</span>
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h2 id="解析" tabindex="-1"><a class="header-anchor" href="#解析" aria-hidden="true">#</a> 解析</h2>
<div class="custom-container info">
<p class="custom-container-title">相关信息</p>
<p>由于输入的两个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。<br>
我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n1,n2，进位值为 carry，则它们的和为 n1+n2+carry；其中，答案链表处相应位置的数字为 (n1+n2+carry)mod10，而新的进位值为 [ (n1+n2+carry)/10 ]。<br>
如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0 。
此外，如果链表遍历结束后，有 carry&gt;0，还需要在答案链表的后面附加一个节点，节点的值为 carry。</p>
</div>
<p><strong>举个🌰：</strong>
以题中两个链表为例，第一位2 + 5 + 上一节点进位数 = 7，7 / 10 = 0 进位数为0；7 % 10 = 7,  头部节点为7。
第二位4 + 6 + 上一节点的进位数 = 10，10 / 10 = 1，进位数为1；10 % 10 = 0  ，本节点数为 0。
第三位3 + 4 + 上一节点的进位数1 = 7，7 / 10 = 0，进位数为0；7 % 10 = 7 ，本节点数为8。
结果值为7-&gt;0-&gt;8</p>
<p><strong>再举个🌰：</strong>
[9,9,9]和[9,9]两个链表相加
第一位9 + 9 +上一节点的进位数= 18，18 / 10 = 1，进位数= 1；18 % 10 = 8  本节点数= 8；
第二位9 + 9 + 上一节点进位数1 = 19， 19 / 10 = 1，进位数=1；19 % 10 = 9 本节点数= 9；
第三位9 + 0 + 上一节点进位数1 = 10，10 / 10 = 1，进位数=1；10 % 10  = 0 本节点数 = 0；
注意这个地方最后一个节点计算完毕，进位数&gt;0 ，所以需要再追加一位。结果值应该是8-&gt;9-&gt;0-&gt;1。</p>
<div class="custom-container info">
<p class="custom-container-title">相关信息</p>
<p>步骤：
下面就可以解题了，先捋一下解题的步骤：</p>
<ol>
<li>首先要定义两个链表，一个是链表的结果值，也就是头部信息。一个是在循环相加链表时动态赋值的链表。如果不把链表的头部信息单独存放一份，在循环赋值中就会丢失前面的头部信息，只会保存最后一个值。</li>
<li>循环遍历需要相加的两个链表，获取对应的值</li>
<li>计算出本节点的数，和进位数，给我们定义的链表赋值。这里要注意，第一次循环时，需要判断链表头部是否为空，如果为空的话，就给头部赋值。</li>
<li>循环结束后，判断进位数是否为1，是否需要尾部追加。</li>
</ol>
</div>
<div class="language-javascript ext-js line-numbers-mode"><pre v-pre class="language-javascript"><code><span class="token doc-comment comment">/**
 * Definition for singly-linked list.
 * function ListNode(val, next) <span class="token punctuation">{</span>
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * <span class="token punctuation">}</span>
 */</span>
<span class="token doc-comment comment">/**
 * <span class="token keyword">@param</span> <span class="token class-name"><span class="token punctuation">{</span>ListNode<span class="token punctuation">}</span></span> <span class="token parameter">l1</span>
 * <span class="token keyword">@param</span> <span class="token class-name"><span class="token punctuation">{</span>ListNode<span class="token punctuation">}</span></span> <span class="token parameter">l2</span>
 * <span class="token keyword">@return</span> <span class="token class-name"><span class="token punctuation">{</span>ListNode<span class="token punctuation">}</span></span>
 */</span>
<span class="token keyword">var</span> <span class="token function-variable function">addTwoNumbers</span> <span class="token operator">=</span> <span class="token keyword">function</span><span class="token punctuation">(</span><span class="token parameter">l1<span class="token punctuation">,</span> l2</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">let</span> head <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span>  <span class="token comment">//头部信息，也可以理解为最终的结果值</span>
    <span class="token keyword">let</span> tail <span class="token operator">=</span> <span class="token keyword">null</span><span class="token punctuation">;</span> <span class="token comment">// 由题意可知，数字的最高位在链表的最后位，所以需要定义一个 tail 节点，每插入一个节点，获取最新的 tail 节点，以便下次在最后一位插入新节点</span>
    <span class="token keyword">let</span> carry <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> <span class="token comment">// 定义当前的进位变量</span>
    <span class="token comment">// 链接从头开始取的每一个节点刚好为每个数组的最低位节点，所以从头开始遍历链表，以最长的链表长度作为遍历结束条件</span>
    <span class="token comment">// 遍历是从当前节点链表头开始遍历，头放置的是数字的低位，刚好是由低到高遍历，保存进位，高位两个数值长度不一时，补 0 即可</span>
    <span class="token keyword">while</span><span class="token punctuation">(</span>l1<span class="token operator">||</span>l2<span class="token punctuation">)</span><span class="token punctuation">{</span>  <span class="token comment">//循环遍历两个链表</span>
        <span class="token comment">// 如果当前节点不存在，则置为 0</span>
        <span class="token keyword">let</span> n1 <span class="token operator">=</span> l1<span class="token operator">?</span>l1<span class="token punctuation">.</span>val<span class="token operator">:</span><span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">let</span> n2 <span class="token operator">=</span> l2<span class="token operator">?</span>l2<span class="token punctuation">.</span>val<span class="token operator">:</span><span class="token number">0</span><span class="token punctuation">;</span>
        <span class="token keyword">let</span> sum <span class="token operator">=</span> n1<span class="token operator">+</span>n2<span class="token operator">+</span>carry<span class="token punctuation">;</span> <span class="token comment">// 保存同一位下两个值+进位值后的结果</span>
        <span class="token comment">// 获取进位值</span>
        carry <span class="token operator">=</span> Math<span class="token punctuation">.</span><span class="token function">floor</span><span class="token punctuation">(</span>sum<span class="token operator">/</span><span class="token number">10</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
        <span class="token keyword">let</span> x <span class="token operator">=</span> sum <span class="token operator">%</span> <span class="token number">10</span>   <span class="token comment">//本次计算的个位数</span>
        <span class="token keyword">if</span><span class="token punctuation">(</span><span class="token operator">!</span>head<span class="token punctuation">)</span><span class="token punctuation">{</span>
          	<span class="token comment">//先给curr链表赋值并且指定head = tail，后续tail指向next节点重置节点信息时，head不会被重置</span>
            head <span class="token operator">=</span> tail <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span>    <span class="token comment">// head和tall只想同一个栈</span>
        <span class="token punctuation">}</span><span class="token keyword">else</span><span class="token punctuation">{</span>
           <span class="token comment">//头部不为空，指定next节点信息</span>
            tail<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span>x<span class="token punctuation">)</span><span class="token punctuation">;</span>
          	<span class="token comment">//tail链表向后移，为了下一次循环继续给next节点赋值</span>
            tail <span class="token operator">=</span> tail<span class="token punctuation">.</span>next
        <span class="token punctuation">}</span>
        <span class="token comment">// 同理，l1和l2链表向后移，获取下一节点信息</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>l1<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            l1 <span class="token operator">=</span> l1<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
        <span class="token keyword">if</span> <span class="token punctuation">(</span>l2<span class="token punctuation">)</span> <span class="token punctuation">{</span>
            l2 <span class="token operator">=</span> l2<span class="token punctuation">.</span>next<span class="token punctuation">;</span>
        <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token comment">// 最后输出时，判断是否还有进位值，如果还有，则继续加到链表的最后一位</span>
    <span class="token keyword">if</span><span class="token punctuation">(</span>carry<span class="token operator">></span><span class="token number">0</span><span class="token punctuation">)</span><span class="token punctuation">{</span>
        tail<span class="token punctuation">.</span>next <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span>carry<span class="token punctuation">)</span><span class="token punctuation">;</span>
    <span class="token punctuation">}</span>
    <span class="token comment">// 返回整个链表</span>
    <span class="token keyword">return</span> head
<span class="token punctuation">}</span><span class="token punctuation">;</span>
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><h2 id="链表解析" tabindex="-1"><a class="header-anchor" href="#链表解析" aria-hidden="true">#</a> 链表解析</h2>
<p>链表是由数据+指针构造而成的，指针指向下一个节点的数据。如下图<img src="https://cdn.nlark.com/yuque/0/2022/jpeg/22237276/1664103552847-83335df5-35af-46e2-9514-24582cef248f.jpeg#clientId=u2a5ca70a-c817-4&amp;crop=0&amp;crop=0&amp;crop=1&amp;crop=1&amp;from=drop&amp;id=ub0781097&amp;margin=[object Object]&amp;name=4e9e245c01dea702eaff5be0bfc7b995.jpg&amp;originHeight=168&amp;originWidth=720&amp;originalType=binary&amp;ratio=1&amp;rotation=0&amp;showTitle=false&amp;size=13338&amp;status=done&amp;style=none&amp;taskId=uca881413-24b0-4877-b84e-12b0b85cbdf&amp;title=" alt="4e9e245c01dea702eaff5be0bfc7b995.jpg" loading="lazy">
所以我们在定义ListNode结构的时候，就需要定义两个属性，一个是当前节点的值，一个是下一个节点的ListNode类型的值，用来实现指针的功能。</p>
<div class="language-javascript ext-js line-numbers-mode"><pre v-pre class="language-javascript"><code><span class="token keyword">class</span> <span class="token class-name">ListNode</span><span class="token punctuation">{</span>
    int val<span class="token punctuation">;</span>   <span class="token comment">//数据</span>
    ListNode next<span class="token punctuation">;</span>   <span class="token comment">//指向下一个节点的数据</span>
<span class="token punctuation">}</span>
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>以加上构造函数：</p>
<div class="language-javascript ext-js line-numbers-mode"><pre v-pre class="language-javascript"><code><span class="token keyword">class</span> <span class="token class-name">ListNode</span><span class="token punctuation">{</span>
    int val<span class="token punctuation">;</span>
    ListNode next<span class="token punctuation">;</span>
    <span class="token function">ListNode</span><span class="token punctuation">(</span><span class="token parameter">int x</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> val <span class="token operator">=</span> x<span class="token punctuation">;</span> <span class="token punctuation">}</span>
    <span class="token function">ListNode</span><span class="token punctuation">(</span><span class="token parameter">int x<span class="token punctuation">,</span> ListNode y</span><span class="token punctuation">)</span> <span class="token punctuation">{</span> val <span class="token operator">=</span> x<span class="token punctuation">;</span> next <span class="token operator">=</span> y<span class="token punctuation">;</span> <span class="token punctuation">}</span>
<span class="token punctuation">}</span>
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div><div class="line-number"></div></div></div><p>假如说要定义[2, 4, 6]这么一个链表，也可以这么赋值，这样我感觉会更清晰的理解到链表的结构。</p>
<div class="language-javascript ext-js line-numbers-mode"><pre v-pre class="language-javascript"><code>ListNode l1 <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span><span class="token number">2</span><span class="token punctuation">,</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span><span class="token number">4</span><span class="token punctuation">,</span> <span class="token keyword">new</span> <span class="token class-name">ListNode</span><span class="token punctuation">(</span><span class="token number">6</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">;</span>
</code></pre><div class="line-numbers" aria-hidden="true"><div class="line-number"></div></div></div></div></template>


